home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / digital marsC compier / dm / stl / stl_queue.h < prev    next >
Encoding:
C/C++ Source or Header  |  2000-06-08  |  7.4 KB  |  244 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996,1997
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26.  
  27. /* NOTE: This is an internal header file, included by other STL headers.
  28.  *   You should not attempt to use it directly.
  29.  */
  30.  
  31. #ifndef __SGI_STL_INTERNAL_QUEUE_H
  32. #define __SGI_STL_INTERNAL_QUEUE_H
  33.  
  34. #include <sequence_concepts.h>
  35.  
  36. __STL_BEGIN_NAMESPACE
  37.  
  38. // Forward declarations of operators < and ==, needed for friend declaration.
  39.  
  40. template <class _Tp, 
  41.           class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(deque<_Tp>) >
  42. class queue;
  43.  
  44. template <class _Tp, class _Seq>
  45. inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  46.  
  47. template <class _Tp, class _Seq>
  48. inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  49.  
  50.  
  51. template <class _Tp, class _Sequence>
  52. class queue {
  53.  
  54.   // requirements:
  55.  
  56.   __STL_CLASS_REQUIRES(_Tp, _Assignable);
  57.   __STL_CLASS_REQUIRES(_Sequence, _FrontInsertionSequence);
  58.   __STL_CLASS_REQUIRES(_Sequence, _BackInsertionSequence);
  59.   typedef typename _Sequence::value_type _Sequence_value_type;
  60.   __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
  61.  
  62.  
  63. #ifdef __STL_MEMBER_TEMPLATES 
  64.   template <class _Tp1, class _Seq1>
  65.   friend bool operator== (const queue<_Tp1, _Seq1>&,
  66.                           const queue<_Tp1, _Seq1>&);
  67.   template <class _Tp1, class _Seq1>
  68.   friend bool operator< (const queue<_Tp1, _Seq1>&,
  69.                          const queue<_Tp1, _Seq1>&);
  70. #else /* __STL_MEMBER_TEMPLATES */
  71.   friend bool __STD_QUALIFIER
  72.   operator== __STL_NULL_TMPL_ARGS (const queue&, const queue&);
  73.   friend bool __STD_QUALIFIER
  74.   operator<  __STL_NULL_TMPL_ARGS (const queue&, const queue&);
  75. #endif /* __STL_MEMBER_TEMPLATES */
  76.  
  77. public:
  78.   typedef typename _Sequence::value_type      value_type;
  79.   typedef typename _Sequence::size_type       size_type;
  80.   typedef          _Sequence                  container_type;
  81.  
  82.   typedef typename _Sequence::reference       reference;
  83.   typedef typename _Sequence::const_reference const_reference;
  84. protected:
  85.   _Sequence c;
  86. public:
  87.   queue() : c() {}
  88.   explicit queue(const _Sequence& __c) : c(__c) {}
  89.  
  90.   bool empty() const { return c.empty(); }
  91.   size_type size() const { return c.size(); }
  92.   reference front() { return c.front(); }
  93.   const_reference front() const { return c.front(); }
  94.   reference back() { return c.back(); }
  95.   const_reference back() const { return c.back(); }
  96.   void push(const value_type& __x) { c.push_back(__x); }
  97.   void pop() { c.pop_front(); }
  98. };
  99.  
  100. template <class _Tp, class _Sequence>
  101. bool 
  102. operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  103. {
  104.   return __x.c == __y.c;
  105. }
  106.  
  107. template <class _Tp, class _Sequence>
  108. bool
  109. operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  110. {
  111.   return __x.c < __y.c;
  112. }
  113.  
  114. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  115.  
  116. template <class _Tp, class _Sequence>
  117. bool
  118. operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  119. {
  120.   return !(__x == __y);
  121. }
  122.  
  123. template <class _Tp, class _Sequence>
  124. bool 
  125. operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  126. {
  127.   return __y < __x;
  128. }
  129.  
  130. template <class _Tp, class _Sequence>
  131. bool 
  132. operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  133. {
  134.   return !(__y < __x);
  135. }
  136.  
  137. template <class _Tp, class _Sequence>
  138. bool 
  139. operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  140. {
  141.   return !(__x < __y);
  142. }
  143.  
  144. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  145.  
  146. template <class _Tp, 
  147.           class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
  148.           class _Compare
  149.           __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) >
  150. class priority_queue {
  151.  
  152.   // requirements:
  153.  
  154.   __STL_CLASS_REQUIRES(_Tp, _Assignable);
  155.   __STL_CLASS_REQUIRES(_Sequence, _Sequence);
  156.   __STL_CLASS_REQUIRES(_Sequence, _RandomAccessContainer);
  157.   typedef typename _Sequence::value_type _Sequence_value_type;
  158.   __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type);
  159.   __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp);
  160.  
  161. public:
  162.   typedef typename _Sequence::value_type      value_type;
  163.   typedef typename _Sequence::size_type       size_type;
  164.   typedef          _Sequence                  container_type;
  165.  
  166.   typedef typename _Sequence::reference       reference;
  167.   typedef typename _Sequence::const_reference const_reference;
  168. protected:
  169.   _Sequence c;
  170.   _Compare comp;
  171. public:
  172.   priority_queue() : c() {}
  173.   explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
  174.   priority_queue(const _Compare& __x, const _Sequence& __s) 
  175.     : c(__s), comp(__x) 
  176.     { make_heap(c.begin(), c.end(), comp); }
  177.  
  178. #ifdef __STL_MEMBER_TEMPLATES
  179.   template <class _InputIterator>
  180.   priority_queue(_InputIterator __first, _InputIterator __last) 
  181.     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
  182.  
  183.   template <class _InputIterator>
  184.   priority_queue(_InputIterator __first, 
  185.                  _InputIterator __last, const _Compare& __x)
  186.     : c(__first, __last), comp(__x) 
  187.     { make_heap(c.begin(), c.end(), comp); }
  188.  
  189.   template <class _InputIterator>
  190.   priority_queue(_InputIterator __first, _InputIterator __last,
  191.                  const _Compare& __x, const _Sequence& __s)
  192.   : c(__s), comp(__x)
  193.   { 
  194.     c.insert(c.end(), __first, __last);
  195.     make_heap(c.begin(), c.end(), comp);
  196.   }
  197.  
  198. #else /* __STL_MEMBER_TEMPLATES */
  199.   priority_queue(const value_type* __first, const value_type* __last) 
  200.     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
  201.  
  202.   priority_queue(const value_type* __first, const value_type* __last, 
  203.                  const _Compare& __x) 
  204.     : c(__first, __last), comp(__x)
  205.     { make_heap(c.begin(), c.end(), comp); }
  206.  
  207.   priority_queue(const value_type* __first, const value_type* __last, 
  208.                  const _Compare& __x, const _Sequence& __c)
  209.     : c(__c), comp(__x) 
  210.   { 
  211.     c.insert(c.end(), __first, __last);
  212.     make_heap(c.begin(), c.end(), comp);
  213.   }
  214. #endif /* __STL_MEMBER_TEMPLATES */
  215.  
  216.   bool empty() const { return c.empty(); }
  217.   size_type size() const { return c.size(); }
  218.   const_reference top() const { return c.front(); }
  219.   void push(const value_type& __x) {
  220.     __STL_TRY {
  221.       c.push_back(__x); 
  222.       push_heap(c.begin(), c.end(), comp);
  223.     }
  224.     __STL_UNWIND(c.clear());
  225.   }
  226.   void pop() {
  227.     __STL_TRY {
  228.       pop_heap(c.begin(), c.end(), comp);
  229.       c.pop_back();
  230.     }
  231.     __STL_UNWIND(c.clear());
  232.   }
  233. };
  234.  
  235. // no equality is provided
  236.  
  237. __STL_END_NAMESPACE
  238.  
  239. #endif /* __SGI_STL_INTERNAL_QUEUE_H */
  240.  
  241. // Local Variables:
  242. // mode:C++
  243. // End:
  244.